package datastruct

import "sync"

type ListNode struct {
	Pre, Next *ListNode
	Value     string
}
type DoubleList struct {
	Head *ListNode
	Tail *ListNode
	Len  int
	lock sync.Mutex
}

// 获取节点值
func (node *ListNode) GetValue() string {
	return node.Value
}

// 获取节点前驱节点
func (node *ListNode) GetPre() *ListNode {
	return node.Pre
}

// 获取节点后驱节点
func (node *ListNode) GetNext() *ListNode {
	return node.Next
}

// 是否存在后驱节点
func (node *ListNode) HashNext() bool {
	return node.Next != nil
}

// 是否存在前驱节点
func (node *ListNode) HashPre() bool {
	return node.Pre != nil
}

// 是否为空节点
func (node *ListNode) IsNil() bool {
	return node == nil
}

// 添加节点到链表头部的第N个元素之前，N=0表示新节点成为新的头部
func (list *DoubleList) AddNodeFromHead(n int, v string) {
	// 加并发锁
	list.lock.Lock()
	defer list.lock.Unlock()

	// 索引超过列表长度，一定找不到，panic
	if n > list.Len {
		panic("index out")
	}

	// 先找出头部
	node := list.Head

	// 往后遍历拿到第 N+1 个位置的元素
	for i := 1; i <= n; i++ {
		node = node.Next
	}

	// 新节点
	newNode := new(ListNode)
	newNode.Value = v

	// 如果定位到的节点为空，表示列表为空，将新节点设置为新头部和新尾部
	if node.IsNil() {
		list.Head = newNode
		list.Tail = newNode
	} else {
		// 定位到的节点，它的前驱
		Pre := node.Pre

		// 如果定位到的节点前驱为nil，那么定位到的节点为链表头部，需要换头部
		if Pre.IsNil() {
			// 将新节点链接在老头部之前
			newNode.Next = node
			node.Pre = newNode
			// 新节点成为头部
			list.Head = newNode
		} else {
			// 将新节点插入到定位到的节点之前
			// 定位到的节点的前驱节点 Pre 现在链接到新节点上
			Pre.Next = newNode
			newNode.Pre = Pre

			// 定位到的节点的后驱节点 node.Next 现在链接到新节点上
			node.Next.Pre = newNode
			newNode.Next = node.Next

		}

	}

	// 列表长度+1
	list.Len = list.Len + 1
}

// 添加节点到链表尾部的第N个元素之后，N=0表示新节点成为新的尾部
func (list *DoubleList) AddNodeFromTail(n int, v string) {
	// 加并发锁
	list.lock.Lock()
	defer list.lock.Unlock()

	// 索引超过列表长度，一定找不到，panic
	if n > list.Len {
		panic("index out")
	}

	// 先找出尾部
	node := list.Tail

	// 往前遍历拿到第 N+1 个位置的元素
	for i := 1; i <= n; i++ {
		node = node.Pre
	}

	// 新节点
	newNode := new(ListNode)
	newNode.Value = v

	// 如果定位到的节点为空，表示列表为空，将新节点设置为新头部和新尾部
	if node.IsNil() {
		list.Head = newNode
		list.Tail = newNode
	} else {
		// 定位到的节点，它的后驱
		Next := node.Next

		// 如果定位到的节点后驱为nil，那么定位到的节点为链表尾部，需要换尾部
		if Next.IsNil() {
			// 将新节点链接在老尾部之后
			node.Next = newNode
			newNode.Pre = node

			// 新节点成为尾部
			list.Tail = newNode
		} else {
			// 将新节点插入到定位到的节点之后
			// 新节点链接到定位到的节点之后
			newNode.Pre = node
			node.Next = newNode

			// 定位到的节点的后驱节点链接在新节点之后
			newNode.Next = Next
			Next.Pre = newNode

		}

	}

	// 列表长度+1
	list.Len = list.Len + 1
}

// 从头部开始往后找，获取第N+1个位置的节点，索引从0开始。
func (list *DoubleList) IndexFromHead(n int) *ListNode {
	// 索引超过或等于列表长度，一定找不到，返回空指针
	if n >= list.Len {
		return nil
	}

	// 获取头部节点
	node := list.Head

	// 往后遍历拿到第 N+1 个位置的元素
	for i := 1; i <= n; i++ {
		node = node.Next
	}

	return node
}

// 从尾部开始往前找，获取第N+1个位置的节点，索引从0开始。
func (list *DoubleList) IndexFromTail(n int) *ListNode {
	// 索引超过或等于列表长度，一定找不到，返回空指针
	if n >= list.Len {
		return nil
	}

	// 获取尾部节点
	node := list.Tail

	// 往前遍历拿到第 N+1 个位置的元素
	for i := 1; i <= n; i++ {
		node = node.Pre
	}

	return node
}

// 从头部开始往后找，获取第N+1个位置的节点，并移除返回
func (list *DoubleList) PopFromHead(n int) *ListNode {
	// 加并发锁
	list.lock.Lock()
	defer list.lock.Unlock()

	// 索引超过或等于列表长度，一定找不到，返回空指针
	if n >= list.Len {
		return nil
	}

	// 获取头部
	node := list.Head

	// 往后遍历拿到第 N+1 个位置的元素
	for i := 1; i <= n; i++ {
		node = node.Next
	}

	// 移除的节点的前驱和后驱
	Pre := node.Pre
	Next := node.Next

	// 如果前驱和后驱都为nil，那么移除的节点为链表唯一节点
	if Pre.IsNil() && Next.IsNil() {
		list.Head = nil
		list.Tail = nil
	} else if Pre.IsNil() {
		// 表示移除的是头部节点，那么下一个节点成为头节点
		list.Head = Next
		Next.Pre = nil
	} else if Next.IsNil() {
		// 表示移除的是尾部节点，那么上一个节点成为尾节点
		list.Tail = Pre
		Pre.Next = nil
	} else {
		// 移除的是中间节点
		Pre.Next = Next
		Next.Pre = Pre
	}

	// 节点减一
	list.Len = list.Len - 1
	return node
}

// 从尾部开始往前找，获取第N+1个位置的节点，并移除返回
func (list *DoubleList) PopFromTail(n int) *ListNode {
	// 加并发锁
	list.lock.Lock()
	defer list.lock.Unlock()

	// 索引超过或等于列表长度，一定找不到，返回空指针
	if n >= list.Len {
		return nil
	}

	// 获取尾部
	node := list.Tail

	// 往前遍历拿到第 N+1 个位置的元素
	for i := 1; i <= n; i++ {
		node = node.Pre
	}

	// 移除的节点的前驱和后驱
	Pre := node.Pre
	Next := node.Next

	// 如果前驱和后驱都为nil，那么移除的节点为链表唯一节点
	if Pre.IsNil() && Next.IsNil() {
		list.Head = nil
		list.Tail = nil
	} else if Pre.IsNil() {
		// 表示移除的是头部节点，那么下一个节点成为头节点
		list.Head = Next
		Next.Pre = nil
	} else if Next.IsNil() {
		// 表示移除的是尾部节点，那么上一个节点成为尾节点
		list.Tail = Pre
		Pre.Next = nil
	} else {
		// 移除的是中间节点
		Pre.Next = Next
		Next.Pre = Pre
	}

	// 节点减一
	list.Len = list.Len - 1
	return node
}
